1. Field of the Invention
This invention relates to computing systems and more particularly to parallelization of software loops and speculative execution thereof.
2. Description of the Relevant Art
In computing systems employing multi-threaded parallel execution, the runtime of a software application may be reduced if two or more iterations of a loop in the software application can be executed in parallel. For example, it may be advantageous to dispatch a separate thread to execute each of two or more iterations of the loop in parallel. In the ideal scenario, each iteration may be executed independently by a separate thread without interference from any other iterations, thus producing a linear speedup in runtime dependent on the number of available hardware threads (strands) or CPU cores. However, in many cases the iterations of a loop may be dependent on each other. For example, a load operation in one iteration may be dependent on the result of a store operation of another iteration (e.g., a store operation in what would have been a previous iteration, if the iterations were executed in their original sequence.)
Compiler analysis can be used to in an attempt to determine the dependencies between the iterations of a loop. However, loop parallelization is often hampered by imprecise compiler analysis, as complete alias and dependence analysis can be costly and very difficult to achieve. Thread speculation can compensate for imprecise alias and dependence information, in some cases. However, prior art techniques employ speculative loop parallelization in an optimistic fashion, with periodic correctness checking during execution or at the end of each iteration of the loop. If the speculation proves to be incorrect, the speculative execution is either rolled back or discarded, therefore the execution resources have been wasted. Prior art approaches are also limited in that they often require a large table to maintain all store information, including store addresses and store values, for each speculative thread.